package 力扣日常刷题.木22二月.第21天227;

/**
 * @author 帅小伙
 * @date 2022/2/27
 * @description
 */
public class Demo173 {

    public static void main(String[] args) {
        int[][] tires = {{2,3},{3,4}};

        minimumFinishTime(tires,5,4);
    }

    public static int minimumFinishTime(int[][] tires, int changeTime, int numLaps) {
        long[] min = new long[numLaps];
        for (int i = 0; i < numLaps; i++) {
            min[i] = Integer.MAX_VALUE;
        }
        for (int[] tire : tires) {
            for (long i = 0, f = tire[0], s = tire[0]; i < numLaps && s < Integer.MAX_VALUE; i++, s += f *= tire[1]) {
                min[(int) i] = Math.min(min[(int) i], s);
            }
        }
        for (int i = 0; i < numLaps; i++) {
            for (int j = 0; j < i; j++) {
                min[i] = Math.min(min[i], min[j] + min[i - j - 1] + changeTime);
            }
        }
        return (int) min[numLaps - 1];

    }

}
